﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Xml.Linq;

namespace MachineLearning {
    class ID3 : DecisionTree {

        public ID3(string fileName) : base(fileName) {
            _attributeList.RemoveAt(_attributeList.Count - 1);
            Tree t = runID3(_trainingData, _targetConcept, _attributeList, "");
        }

        Tree runID3(IEnumerable<XElement> examples, XName target_attribute
            , List<XName> attribute_list, string exp) {
            Tree root = new Tree();
            if (Entropy(examples) == 0.0) {
                if (getPercentPositive() == 1.0) {
                    _expressions.Add("(" + exp.Remove(0, 3) + ")");
                    root.setAttributeName("Yes");
                } else root.setAttributeName("No");
                return root;
            }
            if (attribute_list.Count == 0) {
                //only target attribute exists
                if (getPercentPositive() >= 0.5) {
                    _expressions.Add("(" + exp.Remove(0, 3) + ")");
                    root.setAttributeName("Yes");
                } else root.setAttributeName("No");
                return root;
            }
            //now do main work of algorithm
            XName best = getBestAttribute(examples, attribute_list);
            List<string> p = _dataSet.getPossibleAttributeValues(best);
            root.setAttributeName(best.ToString());
            attribute_list = removeBestAttribute(attribute_list, best);
            exp += " ^ " + best.ToString() + " = ";
            foreach (string s in p) {
                IEnumerable<XElement> subset = _dataSet.refineQuery(examples, best, s);
                Tree t = runID3(subset, target_attribute, attribute_list, (exp + s));
                t.setAttributeValue(s);
                root.Nodes.Add(t);
            }
            return root;
        }

        //cant just call aList.remove because aList is on the heap
        //since ID3 is recursive, we need to keep previous aLists in stack frames
        private List<XName> removeBestAttribute(List<XName> aList, XName best) {
            List<XName> al = new List<XName>();
            foreach (XName a in aList) {
                if (a != best)
                    al.Add(a);
            }
            return al;
        }

        double Gain(IEnumerable<XElement> S, XName A) {
            //iterate through the range of possible values for the attribute
            double entropy = Entropy(S);
            double entropyPrime = 0.0;
            int numberOfExamples = 0;
            int numberOfExamplesWithValue = 0;
            List<string> p = _dataSet.getPossibleAttributeValues(A);
            foreach (string s in p) {
                entropyPrime = Entropy(_dataSet.refineQuery(S, A, s));
                numberOfExamples = _dataSet.getNumberOfExamples(S);
                numberOfExamplesWithValue = _dataSet.getNumberOfExamplesValue(S, A, s);
                entropyPrime *= (double)numberOfExamplesWithValue / (double)numberOfExamples;
                entropy -= entropyPrime;
            }
            return entropy;
        }

        XName getBestAttribute(IEnumerable<XElement> examples, List<XName> attribute_list) {
            XName maxGainAttribute = null;
            XName currentAttribute = null;
            double currentGain = 0.0;
            double maxGain = 0.0;
            for (int i = 0; i < attribute_list.Count; i++) {
                currentAttribute = _dataSet.SampleRowElement.Attribute(attribute_list[i]).Name;
                currentGain = Gain(examples, currentAttribute);
                if (maxGain < currentGain) {
                    maxGain = currentGain;
                    maxGainAttribute = currentAttribute;
                }
            }
            return maxGainAttribute;
        }

	}
}
